package demo8;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-26
 * Time: 9:43
 */
public class Class_Tire {
    public static class Node{
        public int pass;
        public int end ;
        public HashMap<Integer,Node> nexts;
        public Node(){
            this.pass = 0;
            this.end = 0;
            this.nexts = new HashMap<>();
        }

    }

    public static class Tire{
        private Node root;

        public Tire(){
            this.root = new Node();
        }

        public void insert(String words){
            if(words==null) return;
            char[] str = words.toCharArray();
            Node node = root;
            node.pass++;
            int path = 0;
            for(int i =0;i<str.length;++i){
                path = (int)str[i];
                if(!node.nexts.containsKey(path)){
                    node.nexts.put(path,new Node());
                }
                node = node.nexts.get(path);
                node.pass++;
            }
            node.end++;
        }

        public int search(String words){
            if(words == null) return 0;

            char[] str = words.toCharArray();

            Node node = root;
            int path = 0;
            for(int i =0;i<str.length;++i){
                path = (int)str[i];
                if(!node.nexts.containsKey(path)){
                    return 0;
                }
                node = node.nexts.get((path));
            }
            return  node.end;
        }

        public int prefixNumber(String words){
            if(words == null) return 0;

            char[] str = words.toCharArray();
            Node node = root;
            int path = 0;
            for(int i =0;i<str.length;++i){
                path = (int)str[i];
                if(!node.nexts.containsKey(path)){
                    return 0;
                }
                node = node.nexts.get(path);
            }
            return node.pass;
        }

        public void delete(String words){
            if(words==null) return;
            if(search(words)!=0){
                char[] str = words.toCharArray();
                Node node = root;
                node.pass--;
                int path = 0;
                for(int i =0;i<str.length;++i){
                    path = (int)str[i];
                    if(--node.nexts.get(path).pass==0){
                        node.nexts.remove(path);
                    }
                    node.pass--;
                }
                node.end--;
            }
        }

    }


}
